BOJ19539 사과나무

대회당시에 못풀겠어서 이상한 뇌절풀이로 패널티 박다가 팀원한테 넘긴 기억이 있다.

이 문제가 요구하는 관찰이 굉장히 수올스럽기 때문에(뜬금없이 mod 해보는 관찰), 나처럼 수올출신이 아닌 사람은 공식해설 봐도 이해가 안될거라 생각되어 글을 적어본다.

관찰1: mod3 에서 연산을 보면 동시에 +1과 -1 하게 되므로 mod3값의 합이 0이어야 함

관찰2: mod2 에서 연산을 보면 동시에 +1과 +0 하게 되므로 최소한 mod2값의 합 이상 연산이 되었음. 연산은 최대 floor div 2의 합만큼 가능

위의 두 충분조건을 만족하면 필요충분이 됨은 직관이나 공식해설에 나온 증명을 통해 알 수 있음. 풀이 끝

여담으로, BOJ_21045_(Adding Numbers)도 이런 뜬금포mod관찰을 통해 더러운 케이스워크 DP로 풀 수 있는 문제고, 다른 문제는 본적이 없는듯.